/*********************************************************
   Copyright: (C) 2008-2010 by Steven Schveighoffer.
              All rights reserved

   License: Boost Software License version 1.0

   Permission is hereby granted, free of charge, to any person or organization
   obtaining a copy of the software and accompanying documentation covered by
   this license (the "Software") to use, reproduce, display, distribute,
   execute, and transmit the Software, and to prepare derivative works of the
   Software, and to permit third-parties to whom the Software is furnished to
   do so, all subject to the following:

   The copyright notices in the Software and this entire statement, including
   the above license grant, this restriction and the following disclaimer, must
   be included in all copies of the Software, in whole or in part, and all
   derivative works of the Software, unless such copies or derivative works are
   solely in the form of machine-executable object code generated by a source
   language processor.

   THE SOFTWARE IS PROVIDED "AS IS", WITHOUT WARRANTY OF ANY KIND, EXPRESS OR
   IMPLIED, INCLUDING BUT NOT LIMITED TO THE WARRANTIES OF MERCHANTABILITY,
   FITNESS FOR A PARTICULAR PURPOSE, TITLE AND NON-INFRINGEMENT. IN NO EVENT
   SHALL THE COPYRIGHT HOLDERS OR ANYONE DISTRIBUTING THE SOFTWARE BE LIABLE
   FOR ANY DAMAGES OR OTHER LIABILITY, WHETHER IN CONTRACT, TORT OR OTHERWISE,
   ARISING FROM, OUT OF OR IN CONNECTION WITH THE SOFTWARE OR THE USE OR OTHER
   DEALINGS IN THE SOFTWARE.

**********************************************************/
module dcollections.Hash;

private import dcollections.Link;
private import dcollections.model.Iterator;
private import dcollections.DefaultAllocator;

struct HashDefaults
{
    enum float loadFactor = .75;
    enum size_t tableSize = 31;
}

/**
 * Default Hash implementation.  This is used in the Hash* containers by
 * default.
 *
 * The implementation consists of a table of linked lists.  The table index
 * that an element goes in is based on the hash code.
 */
struct Hash(V, alias hashFunction, alias updateFunction, float loadFactor=HashDefaults.loadFactor, size_t startingTableSize=HashDefaults.tableSize, alias Allocator=DefaultAllocator, bool allowDuplicates=false, bool doUpdate=true)
{
    /**
     * alias for Node
     */
    alias Link!(V).Node Node;

    /**
     * alias for the allocator
     */
    alias Allocator!(Link!(V)) allocator;

    /**
     * The allocator for the hash
     */
    allocator alloc;

    /**
     * the table of buckets
     */
    Node[] table;

    /**
     * count of elements in the table
     */
    size_t count;

    // setup does nothing
    void setup() {}

    /**
     * This is like a pointer, used to point to a given element in the hash.
     */
    struct position
    {
        Hash *owner;
        Node ptr;
        ptrdiff_t idx;

        /**
         * Returns the position that comes after p.
         */
        @property inout(position) next() inout
        {
            inout(Link!V)* p_ptr = ptr;
            ptrdiff_t p_idx = idx;
            //position p = this;
            auto table = owner.table;

            if(p_ptr !is null)
            {
                if(p_ptr.next is table[p_idx])
                    //
                    // special case, at the end of a bucket, go to the next
                    // bucket.
                    //
                    p_ptr = null;
                else
                {
                    //
                    // still in the bucket
                    //
                    return inout(position)(owner, p_ptr.next, p_idx);
                }
            }

            //
            // iterated past the bucket, go to the next valid bucket
            //
            while(p_idx < cast(ptrdiff_t)table.length && p_ptr is null)
            {
                if(++p_idx < table.length)
                    p_ptr = table[p_idx];
                else
                    p_ptr = null;
            }
            return inout(position)(owner, p_ptr, p_idx);
        }

        /**
         * Returns the position that comes before p.
         */
        @property inout(position) prev() inout
        {
            inout(Link!V)* p_ptr = ptr;
            ptrdiff_t p_idx = idx;
            //position p = this;
            auto table = owner.table;
            if(p_ptr !is null)
            {
                if(p_ptr is table[p_idx])
                    p_ptr = null;
                else
                    return inout(position)(owner, p_ptr.prev, p_idx);
            }

            while(p_idx > 0 && p_ptr is null)
                p_ptr = table[--p_idx];
            if(p_ptr)
                //
                // go to the end of the new bucket
                //
                p_ptr = p_ptr.prev;
            return inout(position)(owner, p_ptr, p_idx);
        }
    }

    /**
     * return true if the given position is a member of this hash.
     * Easy to determine, since we have to store a pointer to the hash anyways.
     */
    bool belongs(const(position) p) const
    {
        return p.owner is &this;
    }

    /**
     * Add a value to the hash.  Returns true if the value was not present,
     * false if it was updated.
     */
    bool add(V v)
    {
        if(table is null)
            resize(startingTableSize);

        auto h = hashFunction(v) % table.length;
        Node tail = table[h];
        if(tail is null)
        {
            //
            // no node yet, add the new node here
            //
            tail = table[h] = allocate(v);
            Node.attach(tail, tail);
            count++;
            return true;
        }
        else
        {
            static if(!allowDuplicates)
            {
                Node elem = findInBucket(tail, v, tail);
                if(elem is null)
                {
                    count++;
                    tail.prepend(allocate(v));
                    // not single element, need to check load factor
                    checkLoadFactor();
                    return true;
                }
                else
                {
                    //
                    // found the node, set the value instead
                    //
                    static if(doUpdate)
                        updateFunction(elem.value, v);
                    return false;
                }
            }
            else
            {
                //
                // always add, even if the node already exists.
                //
                count++;
                tail.prepend(allocate(v));
                // not single element, need to check load factor
                checkLoadFactor();
                return true;
            }
        }
    }

    /**
     * Resize the hash table to the given capacity.  Normally only called
     * privately.
     */
    void resize(size_t capacity)
    {
        if(capacity > table.length)
        {
            auto newTable = new Node[capacity];

            foreach(head; table)
            {
                if(head)
                {
                    //
                    // make the last node point to null, to mark the end of
                    // the bucket
                    //
                    Node.attach(head.prev, null);
                    for(Node cur = head, next = head.next; cur !is null;
                            cur = next)
                    {
                        next = cur.next;
                        auto h = hashFunction(cur.value) % newTable.length;
                        Node newHead = newTable[h];
                        if(newHead is null)
                        {
                            newTable[h] = cur;
                            Node.attach(cur, cur);
                        }
                        else
                            newHead.prepend(cur);
                    }
                }
            }
            delete table;
            table = newTable;
        }
    }

    /**
     * Check to see whether the load factor dictates a resize is in order.
     */
    void checkLoadFactor()
    {
        if(table !is null)
        {
            float fc = cast(float) count;
            float ft = table.length;

            if(fc / ft > loadFactor)
                resize(2 * cast(size_t)(fc / loadFactor) + 1);
        }
    }

    /**
     * Returns a position that points to the first element in the hash.
     */
    @property inout(position) begin() inout
    {
        if(count == 0)
            return end;
        auto result = inout(position)(&this, null, -1);
        //
        // this finds the first valid node
        //
        return result.next;
    }

    /**
     * Returns a position that points past the last element of the hash.
     */
    @property inout(position) end() inout
    {
        return inout(position)(&this, null, table.length);
    }

    // private function used to implement common pieces
    private inout(Node) findInBucket(inout(Node) bucket, const(V) v, inout(Node) startFrom) inout
    in
    {
        assert(bucket !is null);
    }
    body
    {
        inout(Link!V)* n;
        // this is to work around compiler bug 4088
        static if(is(V == interface))
        {
            if(cast(Object)startFrom.value == cast(Object)v)
                return startFrom;
            for(n = startFrom.next; n !is bucket && cast(Object)n.value != cast(Object)v; n = n.next)
            {
            }
        }
        else
        {
            if(startFrom.value == v)
                return startFrom;
            for(n = startFrom.next; n !is bucket && n.value != v; n = n.next)
            {
            }
        }
        return (n is bucket ? null : n);
    }

    /**
     * Find the first instance of a value
     */
    inout(position) find(const(V) v) inout
    {
        if(count == 0)
            return end;
        auto h = hashFunction(v) % table.length;
        // if bucket is empty, or doesn't contain v, return end
        inout(Link!V)* ptr;
        if(table[h] is null || (ptr = findInBucket(table[h], v, table[h])) is null)
            return end;
        return inout(position)(&this, ptr, h);
    }

    /**
     * Remove a given position from the hash.
     */
    position remove(position pos)
    {
        position retval = pos.next;
        if(pos.ptr is table[pos.idx])
        {
            if(pos.ptr.next is pos.ptr)
                table[pos.idx] = null;
            else
                table[pos.idx] = pos.ptr.next;
        }
        pos.ptr.unlink();
        static if(allocator.freeNeeded)
            alloc.free(pos.ptr);
        count--;
        return retval;
    }

    /**
     * Remove all values from the hash
     */
    void clear()
    {
        static if(allocator.freeNeeded)
            alloc.freeAll();
        delete table;
        table = null;
        count = 0;
    }

    /**
     * keep only elements that appear in subset
     *
     * returns the number of elements removed
     */
    size_t intersect(Iterator!(V) subset)
    {
        if(count == 0)
            return 0;
        //
        // start out removing all nodes, then filter out ones that are in the
        // set.
        //
        auto result = count;
        auto tmp = new Node[table.length];

        foreach(ref v; subset)
        {
            position p = find(v);
            if(p.idx != table.length)
            {
                //
                // found the node in the current table, add it to the new
                // table.
                //
                Node head = tmp[p.idx];

                //
                // need to update the table pointer if this is the head node in that cell
                //
                if(p.ptr is table[p.idx])
                {
                    if(p.ptr.next is p.ptr)
                        table[p.idx] = null;
                    else
                        table[p.idx] = p.ptr.next;
                }

                if(head is null)
                {
                    tmp[p.idx] = p.ptr.unlink();
                    Node.attach(p.ptr, p.ptr);
                }
                else
                    head.prepend(p.ptr.unlink());
                result--;
            }
        }

        static if(allocator.freeNeeded)
        {
            //
            // now, we must free all the unused nodes
            //
            foreach(head; table)
            {
                if(head !is null)
                {
                    //
                    // since we will free head, mark the end of the list with
                    // a null pointer
                    //
                    Node.attach(head.prev, null);
                    while(head !is null)
                    {
                        auto newhead = head.next;
                        alloc.free(head);
                        head = newhead;
                    }
                }
            }
        }
        table = tmp;
        count -= result;
        return result;
    }

    static if(allowDuplicates)
    {
        /**
         * count the number of times a given value appears in the hash
         */
        size_t countAll(const(V) v) const
        {
            auto p = find(v);
            const(Link!V)* p_ptr = p.ptr;
            ptrdiff_t p_idx = p.idx;
            size_t result = 0;
            if(p_idx != table.length)
            {
                auto bucket = table[p_idx];
                do
                {
                    if(p_ptr.value == v)
                        result++;

                    p_ptr = p_ptr.next;
                }
                while(p_ptr !is bucket);
            }
            return result;
        }

        /**
         * remove all the instances of v that appear in the hash
         */
        size_t removeAll(V v)
        {
            position p = find(v);
            size_t result = 0;
            if(p.idx != table.length)
            {
                auto bucket = table[p.idx];
                if(bucket is p.ptr)
                {
                    while(p.ptr && p.ptr.value == v)
                    {
                        result++;
                        if((bucket = p.ptr.next) is p.ptr)
                            bucket = null;
                        p.ptr.unlink();
                        static if(allocator.freeNeeded)
                        {
                            alloc.free(p.ptr);
                        }
                        p.ptr = bucket;
                    }
                    table[p.idx] = bucket;
                    if(!p.ptr)
                    {
                        count -= result;
                        return result;
                    }
                }
                do
                {
                    if(p.ptr.value == v)
                    {
                        result++;
                        auto orig = p.ptr;
                        p.ptr = p.ptr.next;
                        orig.unlink();
                        static if(allocator.freeNeeded)
                        {
                            alloc.free(orig);
                        }
                    }
                    else
                        p.ptr = p.ptr.next;
                }
                while(p.ptr !is bucket);
            }
            return result;
        }

        /**
         * Find a given value in the hash, starting from the given position.
         * If the position is beyond the last instance of v (which can be
         * determined if the position's bucket is beyond the bucket where v
         * should go), then end is returned.
         */
        inout(position) find(V v, inout(position) startFrom) inout
        {
            if(count == 0)
                return end;
            auto h = hashFunction(v) % table.length;
            inout(Link!V)* ptr = startFrom.ptr;
            if(startFrom.idx < h)
            {
                // if bucket is empty, return end
                if(table[h] is null)
                    return end;

                // start from the bucket that the value would live in
                ptr = table[h];
            }
            else if(startFrom.idx > h)
                // beyond the bucket, return end
                return end;

            if((ptr = findInBucket(table[h], v, ptr)) !is
                    null)
                return inout(position)(&this, ptr, h);
            return end;
        }
    }

    /**
     * copy all the elements from this hash to target.
     */
    void copyTo(ref Hash target)
    {
        //
        // copy all local values
        //
        target = this;

        //
        // reset allocator
        //
        target.alloc = target.alloc.init;

        //
        // reallocate all the nodes in the table
        //
        target.table = new Node[table.length];
        foreach(i, n; table)
        {
            if(n !is null)
                target.table[i] = n.dup(&target.allocate);
        }
    }

    Node allocate()
    {
        return alloc.allocate();
    }

    Node allocate(V v)
    {
        auto result = allocate();
        result.value = v;
        return result;
    }
}

/**
 * used to define a Hash that does not perform updates
 */
template HashNoUpdate(V, alias hashFunction, float loadFactor=HashDefaults.loadFactor, size_t startingTableSize=HashDefaults.tableSize, alias Allocator=DefaultAllocator)
{
    // note the second hashFunction isn't used because doUpdates is false
    alias Hash!(V, hashFunction, hashFunction, loadFactor, startingTableSize, Allocator, false, false) HashNoUpdate;
}

/**
 * used to define a Hash that takes duplicates
 */
template HashDup(V, alias hashFunction, float loadFactor=HashDefaults.loadFactor, size_t startingTableSize=HashDefaults.tableSize, alias Allocator=DefaultAllocator)
{
    // note the second hashFunction isn't used because doUpdates is false
    alias Hash!(V, hashFunction, hashFunction, loadFactor, startingTableSize, Allocator, true, false) HashDup;
}
